package datatypes.kdTree;

import java.awt.Color;
import java.util.Arrays;

import controller.Globals;
import datatypes.Vertex;

/**
 * KdTreeElements are the building blocks of a KdTree.
 * Both leaves and nodes are KdTreeElements. A leaf is just a
 * KdTreeElement with both left and right sub-elements being null (which
 * can be queried using {@link #isLeaf()}).
 * 
 * Each KdTreeElement has a reference to it's KdTree container for access
 * to properties common to all elements.
 * 
 * @author nils
 *
 */
public class KdTreeElement {
	private static int nextID = 0;
	
		/** Unique id */
	public int id;
		/** The treeContainer provides access to properties relevant to the whole tree. */
	public KdTree treeContainer;
		/** The depth this element is at */
	public int depth = 0;
		/** The index is the number of this element counting all elements of the same depth starting from the left with the leftmost element being 0. */
	public int index = 0;
		/** Contains max & min values of the bounds for each axis. Handy for making the bounding box! */
	protected Range range;
		/** The children of this KdTreeElement. Both will be null if this is a leaf. */
	public KdTreeElement left, right, parent;
		/** The median the point set has been split at. In case this is a leaf this is the stored point. */
	protected Vertex median;
		/** The 'splitting line' on the current axis.
		 *	Is equal to the value of the median if (treeContainer.interpolateDivider == false),
		 *	otherwise it's halfway between the median value and the value to the right (remember,
		 *	the median will be part of the left subtree). */
	protected double divider;				
	protected KdVertexComparator comparator = new KdVertexComparator(0);
	protected Color color;
		/** used to manage generating tree string for printing to the console */
	private static boolean printing = false;
    private boolean isLeaf;
    private boolean isLeafIsSet = false;
	
	/**
	 * Package protected constructor (made public for unit testing only)
	 * Use KdTree's constructor instead in order to generate a new tree.
	 * @param geometry The geometry to build the tree from
	 * @param treeContainer
	 */
	public KdTreeElement(Vertex[] geometry, KdTree treeContainer) {
		this.id = nextID++;
		this.treeContainer = treeContainer;
		this.range = new Range(treeContainer.dimensions);
		if (geometry != null) {
			this.replaceExistingPointsWith(geometry);
		}
//                this.isLeaf = true;
	}
	
	/**
	 * Constructor for class-internal use only
	 * @param parent
	 * @param median
	 * @param divider
	 * @param left
	 * @param right
	 * @param range
	 */
	protected KdTreeElement(KdTreeElement parent, Vertex median, double divider, KdTreeElement left, KdTreeElement right, Range range) {
		this.id = nextID++;
		this.parent = parent;
		this.treeContainer = parent.treeContainer;
		this.median = median;
		this.divider = divider;
		this.left = left;
		this.right = right;
		this.range = range;
		this.depth = parent.depth + 1;
		if (this.depth > treeContainer.maxDepth) {
			treeContainer.maxDepth = this.depth;
		}
//                updateIsLeaf();
	}
	
	
	
	//**************************************************************
	// growing trees
	//**************************************************************

	/**
	 * Replaces the existing (sub-)tree with a new tree built for the 
	 * points given by the pointSet.
	 * @param geometry
	 */
	public void replaceExistingPointsWith(Vertex[] vertices) {
		setRange(vertices,  0, vertices.length);
		
		// to make sure that the first axis and depth is 0 we temporarily set the axis to
		// -1 here, causing the depth increment to overflow to 0 when building the root element.
		this.depth = -1;
		
		Vertex[][] presortedVertices = new Vertex[treeContainer.dimensions][vertices.length];
		for (int i = 0; i < treeContainer.dimensions; i++) {
			presortedVertices[i] = vertices.clone();
			comparator.setAxis(i);
			Arrays.sort(presortedVertices[i], comparator);
		}
		KdTreeElement newTree = buildKdTree(presortedVertices, 0, vertices.length, range.clone(), 0);
		
		
		// I would have enjoyed doing something like "this = newTree;" here which is no problem in
		// objective-c but doesn't seem to work in java. Apparently we have to copy
		// all properties manually:
		this.median = newTree.median;
		this.divider = newTree.divider;
		this.left = newTree.left;
		this.right = newTree.right;
		this.depth = newTree.depth;
//                this.isLeaf = newTree.isLeaf;
	}
	
	/**
	 * Recursively builds a kd-tree.
	 * @param vectors The points to build the tree from.
	 * @param from Current left limit of the vectors array.
	 * @param to Current right limit of the vectors array.
	 * @param range The current bounding box.
	 * @return The newly generated KdTreeElement. The first caller will get the root element.
	 */
	private KdTreeElement buildKdTree(Vertex[][] vectors, int from, int to, Range range, int index) {
		// the axis of the child elements:
		int axis = (this.depth + 1) % treeContainer.dimensions;
		if (to - from < 1) {
			// oops. This should only happen with empty geometry.
			System.out.println("NULL");
			return null;
		}
		if (to - from == 1) {
			// add leaf:
			KdTreeElement leaf = new KdTreeElement(this, vectors[axis][from], vectors[axis][0].getEntry(axis), null, null, range);
			leaf.index = index;
			return leaf;
		}
		
		int median = from + (to - from - 1) / 2;
		
		// the value of the median of the current axis will be the splitting
		// line. All values <= the median will be in the left-hand sub tree,
		// all others in the right hand one.
		Vertex medianVector = vectors[axis][median];

		Range rangeLeft = range.clone();
		Range rangeRight = range.clone();
		double divider;
		if (Globals.INTERPOLATE_DIVIDER) {
			divider = medianVector.getEntry(axis) + (vectors[axis][median+1].getEntry(axis) - medianVector.getEntry(axis))/2;
		} else {
			divider = medianVector.getEntry(axis);
		}
		rangeLeft.setMax(divider, axis);
		rangeRight.setMin(divider, axis);
		KdTreeElement node = new KdTreeElement(this, medianVector, divider, left, right, range);
		node.treeContainer = treeContainer;
		node.index = index;
		
		/*
		 * We need to reorganize the vectors array so that the vertices
		 * we are handling in the next step are all in the same range of
		 * indices without losing the property of being presorted with
		 * respect to each axis:
		 */
		Vertex[] temp = new Vertex[to - from];
		comparator.setAxis(axis);
		for (int otherAxis = (axis+1)%treeContainer.dimensions; otherAxis != axis; otherAxis = (otherAxis+1)%treeContainer.dimensions) {
			int leftIndex = 0;
			int rightIndex = median-from+1;
			for (int i = from; i < to; i++) {
				Vertex v = vectors[otherAxis][i];
				if (comparator.compare(v, medianVector) <= 0) {
					temp[leftIndex++] = v;
				} else {
					temp[rightIndex++] = v;
				}
			}
			for (int i = from, j = 0; i < to; i++, j++) {
				vectors[otherAxis][i] = temp[j];
			}
		}
		
		node.left = node.buildKdTree(vectors, from, median+1, rangeLeft, index*2);
		node.right = node.buildKdTree(vectors, median+1, to, rangeRight, (index * 2) + 1);
//                node.updateIsLeaf();
		return node;
	}

//        private void updateIsLeaf() {
//            this.isLeaf = left == null && right == null;
//        }
	
	
	
	//**************************************************************
	// accessors
	//**************************************************************
	
	/**
	 * Sets the values for the bounding box of this element.
	 * The bounding box is basically the volume this element is covering.
	 * @param vertices
	 * @param from
	 * @param to
	 */
	public void setRange(Vertex[] vertices, int from, int to) {
		if (this.range == null) {
			this.range = new Range(treeContainer.dimensions);
		}
		for (int axis = 0; axis < treeContainer.dimensions; axis++) {
			comparator.setAxis(axis);
			Arrays.sort(vertices, from, to, comparator);
			this.range.setMax(vertices[to-1].getEntry(axis), axis);
			this.range.setMin(vertices[0].getEntry(axis), axis);
		}
	}
	
	/**
	 * Use {@link datatypes.kdTree.KdTree#getElement(int, int) KdTree's equivalent} instead.
	 * Provides convenient access to a KdTreeElement at the given depth and index.
	 * 
	 * @param depth
	 * @param index
	 * @return
	 */
	public KdTreeElement getElement(int depth, int index) {
		KdTreeElement element = this;
		while (depth > 0) {
			int split = (int) Math.pow(2, depth)/2;
			if (index < split && element != null) {
				element = element.getLeft();
			} else {
				index -= split;
				element = element.getRight();
			}
			if (element == null) {
				return element;
			}
			depth--;
		}
		return element;
	}
	
	/**
	 * Get-accessor to the left subtree.
	 * @return
	 */
	public KdTreeElement getLeft() {
		return left;
	}
	
	/**
	 * Get-accessor to the right subtree.
	 * @return
	 */
	public KdTreeElement getRight() {
		return right;
	}
	
	/**
	 * Get-accessor to the median the splitting line is based on.
	 * @return
	 */
	public Vertex getMedian() {
		return median;
	}
	
	/**
	 * Get-accessor for the axis the median has been split at.
	 * @return
	 */
	public int getAxis() {
		return this.depth % treeContainer.dimensions;
	}
	
	/**
	 * The maximum depth of the tree.
	 * @return
	 */
	public int getMaxDepth() {
		return treeContainer.getMaxDepth();
	}
	
	/**
	 * Facilitates convenient querying for leafyness.
	 * @return
	 */
	public boolean isLeaf() {
		if ( ! isLeafIsSet) {
			isLeaf = (left == null && right == null);
			isLeafIsSet = true;
		}
		return isLeaf;
//		return (left == null && right == null);
	}
	
	/**
	 * Returns the value the tree is split at at this node.
	 * @return
	 */
	public double getDivider() {
		return divider;
	}
	
	
	//**************************************************************
	// console printing
	//**************************************************************
	
	
	/**
	 * Creates a String from the given PdVector[] for printing to the console.
	 * Just used for sysos during development.
	 * @param vectors
	 * @param from
	 * @param to
	 * @return
	 */
	@SuppressWarnings("unused")
	private String arrayString(Vertex[] vectors, int from, int to) {
		StringBuffer buffer = new StringBuffer();
		for (int axis = 0; axis < treeContainer.dimensions; axis++) {
		buffer.append("Axis " + axis + ": ");
		int c = 0;
		for (Vertex vector : vectors) {
			if (c==from) {
				buffer.append("[");
			}
			buffer.append(vector.getEntry(axis));
			if (c == to-1) {
				buffer.append("] ");
			} else {
				buffer.append("  ");
			}
			c++;
		}
		buffer.append("\n");
		}
		return buffer.toString();
	}
	
	/**
	 * Helper method for {@link #toString()}.
	 * @return
	 */
	private String leafString() {
		Vertex median = getMedian();
		if (median == null) {
			return "null";
		}
		return median.toString();
	}
	
	/**
	 * Helper method for {@link #toString()}.
	 * @return
	 */
	private String nodeString() {
		Vertex median = getMedian();
		if (median == null) {
			return "null";
		}
		return "" + median.getEntry(getAxis());
	}
	
	public String toString() {
		if (printing) {
			if (isLeaf()) {
				return leafString();
			} else {
				return nodeString();
			}
		}
		printing = true;
		String accString = "kd-tree (rotated 90° CCW):";
		accString += treeToString(this,-6,"");
		printing = false;
		return accString;
	}
	
	/**
	 * Helper method for {@link #toString()}.
	 * @return
	 */
	private static String offset(int indent) {
		StringBuffer buffer = new StringBuffer();
		for(int i=0;i<indent;i++) buffer.append(" ");
		return buffer.toString();
	}		
	
	/**
	 * Helper method for {@link #toString()}.
	 * @return
	 */
	private String treeToString(KdTreeElement x, int indent, String connector) {
		String result = "";
		KdTreeElement current = x;
		if(current!=null) {
			result += treeToString(current.getRight(),indent+6,"╭━━ ")+"\n"+offset(indent)+
			   connector + current +
			   treeToString(current.getLeft(),indent+6,"╰━━ ");
		}
		return result;
	}

}
